/**
 * //设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。
 * //
 * // 以下是井字游戏的规则：
 * //
 * //
 * // 玩家轮流将字符放入空位（" "）中。
 * // 第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
 * // "X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
 * // 当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
 * // 当所有位置非空时，也算为游戏结束。
 * // 如果游戏结束，玩家不允许再放置字符。
 * //
 * //
 * // 如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"X"或"O"）；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回
 * //"Pending"。
 * //
 * // 示例 1：
 * //
 * // 输入： board = ["O X"," XO","X O"]
 * //输出： "X"
 * //
 * //
 * // 示例 2：
 * //
 * // 输入： board = ["OOX","XXO","OXO"]
 * //输出： "Draw"
 * //解释： 没有玩家获胜且不存在空位
 * //
 * //
 * // 示例 3：
 * //
 * // 输入： board = ["OOX","XXO","OX "]
 * //输出： "Pending"
 * //解释： 没有玩家获胜且仍存在空位
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= board.length == board[i].length <= 100
 * // 输入一定遵循井字棋规则
 * //
 * // Related Topics 数组 计数 矩阵 👍 33 👎 0
 */

package com.xixi.medium;

public class ID_Interview_16_04_TicTacToeLcci {
    public static void main(String[] args) {
        Solution solution = new ID_Interview_16_04_TicTacToeLcci().new Solution();
        System.out.println(
                solution.tictactoe(new String[]{"XOX", "OOX", "OXO"})
        );

    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {


        boolean finished = true; //是否结束,初始假设都填满了
        boolean hasWon = true; //是否出现胜利者

        public String tictactoe(String[] board) {

            if (board.length == 1) {
                char onlyChar = board[0].toCharArray()[0];
                if (onlyChar == 'X') {
                    return "X";
                } else if (onlyChar == 'O') {
                    return "O";
                } else {
                    return "Pending";
                }
            }


            return judge(board, board.length);


        }


        public String judge(String[] board, int boardLength) {


            //判断横行
            int i = 0;
            int j = 1;
            while (i < boardLength) {
                j = 1;
                char[] line = board[i].toCharArray();
                hasWon = true; //先假定都相等
                while (j < board[i].length()) {

                    if (line[j - 1] == ' ' || line[j] == ' ') { //出现了空格说明没结束
                        finished = false;
                        hasWon = false;
                        break; //这行不用刚看了
                    }

                    if (line[j - 1] != line[j]) { //没出现空格的情况下，出现不相等就标记false;
                        hasWon = false; //出现不相等的先标记false，还要继续往下探查是否有空格
                    }
                    j++;
                }
                if (hasWon && j == board[i].length()) { //这行遍历到了最后都相等
                    return line[0] + ""; //本行第一个字符
                }
                i++; //判断下一行
            }

            //到最后一行都没有胜利者此时，i==boardLength;

            //判断竖列
            //此时不用在判断是否有空字符
            j = 0;
            while (j < board[0].length()) {
                i = 1;
                hasWon = true; //先假定都相等
                while (i < boardLength) {
                    char[] preLine = board[i - 1].toCharArray();
                    char[] thisLine = board[i].toCharArray();

                    if (preLine[j] == ' ' || thisLine[j] == ' ') { //出现了空格说明没结束,此列也没胜者
                        finished = false;
                        hasWon = false;
                        break; //这列不用刚看了
                    }

                    if (preLine[j] != thisLine[j]) {
                        hasWon = false; //j列有不相等了，就break;
                        break;
                    }

                    i++;
                }

                if (hasWon && i == boardLength) { //这行遍历到了最后都相等
                    return board[0].toCharArray()[j] + ""; //此列第一个字符
                }

                j++;
            }


            //判断左下对角线
            hasWon = true;
            i = 1;
            j = 1;
            while (i < boardLength && j < board[0].length()) {

                char[] preLine = board[i - 1].toCharArray();
                char[] thisLine = board[i].toCharArray();


                if (preLine[j - 1] == ' ' || thisLine[j] == ' ') { //对角线碰到空格就弹出
                    finished = false;
                    hasWon = false;
                    break;
                }

                if (preLine[j - 1] != thisLine[j]) {
                    hasWon = false;
                }


                i++;
                j++;
            }

            if (hasWon) {
                return board[0].toCharArray()[0] + "";
            }

            //判断右上对角线
            hasWon = true;
            i = boardLength - 1;
            j = 0;

            while (i > 0 && j < board[0].length() - 1) {

                char[] preLine = board[i].toCharArray();
                char[] thisLine = board[i - 1].toCharArray();


                if (preLine[j] == ' ' || thisLine[j + 1] == ' ') { //对角线碰到空格就弹出
                    finished = false;
                    hasWon = false;
                    break;
                }

                if (preLine[j] != thisLine[j + 1]) {
                    hasWon = false;
                }


                i--;
                j++;
            }
            if (hasWon) {
                return board[boardLength - 1].toCharArray()[0] + "";
            }

            if (finished) {
                return "Draw";
            }

            return "Pending";

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}